import java.util.Arrays;
import java.util.Stack;

public class TestSort {

    /**
     * 直接插入排序
     * */
    public static void insertSort(int[] array1) {
        //i下标从数组的第二个值开始
        for (int i = 1; i < array1.length ; i++) {
            int tmp = array1[i];//tmp存放i下标的值
            int j = i - 1;//j下标为i的前一个位置
            for (; j >= 0; j--) {
                if (array1[j] > tmp) {
                    //j下标的值大，将j下标的值放到j的下一个位置
                    array1[j + 1] = array1[j];
                }else {
                    //j下标的值较小，j小标的值要直接放到j的下一个位置
                    break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量的后一个位置
            array1[j + 1] = tmp;
        }
    }

    /**
     * 希尔排序（直接排序的优化）
     * */
    public static void shellSort(int[] array2) {
        int gap = array2.length;//为数组的长度 - 为10
        while (gap > 1) {
            gap /= 2;//先是分成了5组，然后是2组，再是1组
            shell(array2, gap);//调用直接插入排序方法
        }
    }

    //实现直接插入排序方法
    public static void shell(int[] array2, int gap) {
        //i下标从第一组的第二个数据开始
        for (int i = gap; i < array2.length ; i++) {
            int tmp = array2[i];//tmp存放i下标的值
            int j = i - gap;//j下标为i-gap个位置
            //j每次-gap个位置
            for (; j >= 0; j-=gap) {
                if (array2[j] > tmp) {
                    //j下标的值大，将j下标的值放到j变量加上一个gap的位置上
                    array2[j + gap] = array2[j];
                }else {
                    //j下标的值较小，j下标的值要直接放到j变量加上一个gap的位置上
                    break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量加上一个gap的位置上
            array2[j + gap] = tmp;
        }
    }

    /**
     * 选择排序1
     */
    public static void selectSort(int[] array3) {
        for (int i = 0; i < array3.length; i++) {
            int minIndex = i;//假设最小值是当前的i下标的值
            for (int j = i + 1; j < array3.length; j++) {
                if (array3[j] < array3[minIndex]) {
                    //更新
                    minIndex = j;//将此时的j下标的值赋给minIndex
                }
            }
            if (i != minIndex) {
                //调用交换的方法交换i下标的值和minIndex的值
                swap(array3, minIndex, i);
            }
        }
    }

    //交换的方法
    public static void swap(int[] array3, int i, int j) {
        int tmp = array3[i];
        array3[i] = array3[j];
        array3[j] = tmp;
    }

    /**
     * 选择排序2
     */
    public static void  selecstSort(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int minIndex = left;//假设最小值在左边
            int maxIndex = left;//假设最大值在左边
            //i下标位于第二个位置
            for (int j = left + 1; j <= right; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
                if (array[j] > array[maxIndex]) {
                    maxIndex = j;
                }
            }
            //把最小值交换到前面
            swap(array, minIndex, left);
            //把最大值交换到前面
            swap(array, maxIndex, right);
            left++;
            right--;
        }
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] array) {
        creatBigHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }
    }

    public static void creatBigHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0 ; parent--) {
            //调用向下调整
            shiftDown(array, parent, array.length);
        }
    }

    //向下调整的方法
    public static void shiftDown(int[] array, int parent, int len) {
        int child = (2 * parent) + 1;
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] array) {
        //最外层控制的是趟数
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flag = true;
                }
            }
            if (flag = false) {
                break;
            }
        }
    }

    /**
     * 快速排序 Hoare版
     */
    public static void quickSort (int[] array) {
        quick(array, 0, array.length -1);
    }

    public static void quick(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //接收基准
        int pivot = partition(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //查找基准的方法
    public static int partition(int[] array, int left, int right) {
        int i = left;//存储第一个数据
        int pivot = array[left];//将第一个数据给pivot
        while (left < right) {
            //要是<=、>=，而不是<、>
            while (left < right && array[right] >= pivot) {
                //右边找比pivot小的
                right--;//--说明没找到
            }
            while (left < right && array[left] <= pivot) {
                //左边找比pivot大的
                left++;//++说明没找到
            }

            swap(array, left, right);//调用方法交换左边和右边的值
        }
        //此时已经遍历完成
        swap(array, left, i);//调用非法交换第一个元素和此时left的值
        return left;//返回的就是找到的基准
    }

    /**
     * 快速排序优化 挖坑法版
     * 优化了查找基准的方法
     */
    public static void quickSorts (int[] array) {
        quick(array, 0, array.length -1);
    }

    public static void quicks(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //接收基准
        int pivot = partition(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //查找基准的方法
    public static int partitions(int[] array, int left, int right) {
        int pivot = array[left];//将坑位的数据   给pivot
        while (left < right) {
            //要是<=、>=，而不是<、>
            while (left < right && array[right] >= pivot) {
                //右边找比pivot小的
                right--;//--说明没找到
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                //左边找比pivot大的
                left++;//++说明没找到
            }
            array[right] = array[left];
        }
        //和原来的 left交换
        array[left] = pivot;
        return left;//返回的就是找到的基准
    }

    /**
     * 快速排序优化 前后指针版
     * 优化了查找基准的方法
     */
    public static void quickSortsx (int[] array) {
        quick(array, 0, array.length -1);
    }

    public static void quicksx(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //接收基准
        int pivot = partition(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //查找基准的方法
    public static int partitionsx(int[] array, int left, int right) {
        int prev = left;//在第一个数据
        int cur = left + 1;//在第二个数据
        while (left <=  right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, cur, prev);//调用方法交换左边和右边的值
            }
            cur++;//指向下一个
        }
        swap(array, prev, left);
        return prev;//返回基准
    }

    /**
     * 快速排序 数组有序的情况
     */
    public static void quickSort1 (int[] array) {
        quick1(array, 0, array.length -1);
    }

    //非递归实现快排
    public static void isNotRecursiveQuickSort (int[] array) {
        //定义栈
        Stack<Integer> stack = new Stack<>();
        //定义开始和结束的位置变量
        int start = 0;//是下标0
        int end = array.length - 1;//是数组长度减1
        int pivot = partition(array, start, end);//调用找基准的方法
        //判断左边是不是只有一个数据
        if (pivot > (start + 1)) {
            //不止一个数据 - 将start和end的下标压入到栈中
            stack.push(start);//压入0下标
            stack.push(pivot - 1);//压入此时的4下标
        }
        //判断右边是不是只有一个数据
        if (pivot < (end - 1)) {
            //此时不止一个数据 - 将start和end下标压入栈中
            stack.push(pivot + 1);//压入此时的6下标
            stack.push(end);//压入此时的9下标
        }
        //栈不为空才可以弹出
        while (!stack.isEmpty()) {
            end = stack.pop();//先弹栈顶给end
            start = stack.pop(); //再弹栈顶给start
            //再次找新的基准和新的区间
            pivot = partition(array, start, end);//调用找基准的方法
            //判断左边是不是只有一个数据
            if (pivot > (start + 1)) {
                //不止一个数据 - 将start和end的下标压入到栈中
                stack.push(start);//压入start下标
                stack.push(pivot - 1);//压入此时的end下标
            }
            //判断右边是不是只有一个数据
            if (pivot < (end - 1)) {
                //此时不止一个数据 - 将start和end下标压入栈中
                stack.push(pivot + 1);//压入此时的start下标
                stack.push(end);//压入此时的end下标
            }
        }
    }

    private static void insertSort(int[] array1, int left, int right) {
        //i下标从数组的左边第二个值开始
        for (int i = left + 1; i <= right ; i++) {
            int tmp = array1[i];//tmp存放i下标的值
            int j = i - 1;//j下标为i的前一个位置
            for (; j >= left; j--) {
                if (array1[j] > tmp) {
                    //j下标的值大，将j下标的值放到j的下一个位置
                    array1[j + 1] = array1[j];
                }else {
                    //j下标的值较小，j小标的值要直接放到j的下一个位置
                    break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量的后一个位置
            array1[j + 1] = tmp;
        }
    }

    public static void quick1(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //快排优化
        if (end - start + 1 >= 15) {
            //对start和end范围内的使用插入排序
            insertSort(array, start, end);
            return;
        }
        //在执行 partition1 前，尽量解决划分不均匀的问题
        int index = findMidValOfIndex(array, start, end);//接受三个数中间大小的值
        swap(array, start, index);
        //接收基准
        int pivot = partition1(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //找中间大小的值 - 三数取中法
    public static int findMidValOfIndex(int[] array, int start, int end){
        //如果数据是有序的情况要将它均分
        int minIndex = (start + end) / 2;
        if (array[start] < array[end]) {
            if (array[minIndex] < array[start]) {
                return start;//返回的是中间值
            } else if (array[minIndex] > array[end]) {
                return end;
            } else {
                return minIndex;
            }
        }else {
            if (array[minIndex] > array[start]) {
                return start;
            } else if (array[minIndex] < array[end]) {
                return end;
            } else {
                return minIndex;
            }
        }
    }

    //查找基准的方法
    public static int partition1(int[] array, int left, int right) {
        int i = left;//存储第一个数据
        int pivot = array[left];//将第一个数据给pivot
        while (left < right) {
            //要是<=、>=，而不是<、>
            while (left < right && array[right] >= pivot) {
                //右边找比pivot小的
                right--;//--说明没找到
            }
            while (left < right && array[left] <= pivot) {
                //左边找比pivot大的
                left++;//++说明没找到
            }

            swap(array, left, right);//调用方法交换左边和右边的值
        }
        //此时已经遍历完成
        swap(array, left, i);//调用非法交换第一个元素和此时left的值
        return left;//返回的就是找到的基准
    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] array) {
        mergeSortChild(array, 0, array.length - 1);
    }

    //分解的方法
    public static void mergeSortChild(int[] array, int left, int right) {
        //分解
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;//中间位置
        mergeSortChild(array, left, mid);//递归1分解左边
        mergeSortChild(array, mid + 1, right);//递归右边
        //开始合并
        mergre(array, left, mid, right);
    }

    //合并的方法
    public static void mergre(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //定义一个数组
        int[] tmpArr = new int[right - left + 1];
        int k = 0;//记录数组下标
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] <= array[s2]) {
                //数组下标加1个 指向下一个
                tmpArr[k++] = array[s1++];
            }else {
                //这是s2小的情况 -将s2的值放到数组中
                tmpArr[k++] = array[s2++];
            }
        }
        //此时是s1或者s2超出区间范围了，但是有可能有一个还未超出范围
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        //此时数组中的数据是有的了 - 此时要将排序好的数组传到原来的数组中
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArr[i];
        }
    }

    /**
     * 归并排序非递归实现
     */
    public static void isNotNotRecursiveMergeSort(int[] array) {
        int gap = 1;//先假定每一个数都是单独有序的
        while (gap < array.length) {
            for (int i = 0; i < array.length; i+=gap * 2 ) {
                int left = i;//左边是i下标的位置
                int mid = left + gap - 1;//中间的位置
                int right = gap + mid;
                //防止right和mid越界
                if(mid >= array.length) {
                    mid = array.length - 1;//放到新位置
                }
                if(right >= array.length) {
                    right = array.length - 1;//放到新位置
                }
                //开始归并 - 调用之前的合并方法
                mergre(array, left, mid, right);
            }
            gap *= 2;
        }
    }

    /**
     * 计数排序
     */
    public static void countSort(int[] array) {
        //遍历数组找到最大值和最小值 - 找到才能确定数组的长度
        int maxVal = array[0];//假设最大值在0下标
        int minVal = array[0];//假设最小值在0下标
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal) {
                //此时i下标的值为最大值
               maxVal = array[i];
            }
            if (array[i] < minVal) {
                //此时i下标为最小值
                minVal = array[i];
            }
        }
        //确定数组的长度
        int len = maxVal - minVal + 1;
        int[] countArr = new int[len];
        //遍历数组统计每个数字出现的次数
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            countArr[val - minVal] ++;
        }
        int index = 0;
        //此时计数完毕 - 看每个下标的值是几就打印几
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                array[index] = i + minVal;
                index++;
                countArr[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {9, 4, 123, 45, 7, 18};//创建数组
        int[] arrays = {789, 654, 321};
        int[] arr = {12, 45, 67, 11, 565};
        int[] countArray = {0, 2, 4, 2, 3, 8, 4, 5, 9, 8};
        //insertSort(array);//调用方法
        //System.out.println("直接插入排序后：" + Arrays.toString(array));//输出排序后的数组

        //shellSort(array);
        //System.out.println("希尔排序排序后：" + Arrays.toString(array));

        //selectSort(array);
        //System.out.println("选择排序后：" + Arrays.toString(array));

        //heapSort(array);
        //System.out.println("堆排序后·：" + Arrays.toString(array));

        //bubbleSort(array);
        //System.out.println("冒泡排序后·：" + Arrays.toString(array));

        //quickSort1(array);
        //System.out.println("快速排序后·：" + Arrays.toString(array));

        //quickSorts(array);
        //System.out.println("快速排序后·：" + Arrays.toString(array));

        //quickSort(array);
        //System.out.println("快速排序后：" + Arrays.toString(array));

        isNotRecursiveQuickSort(arrays);
        System.out.println("非递归实现快排排序后" + Arrays.toString(arrays));

        mergeSort(array);
        System.out.println("归并排序后" + Arrays.toString(array));

        isNotNotRecursiveMergeSort(arr);
        System.out.println("归并排序非递归实现" + Arrays.toString(arr));

        countSort(countArray);
        System.out.println("计数排序后" + Arrays.toString(countArray));
    }
}